/*
 * @lc app=leetcode.cn id=215 lang=cpp
 *
 * [215] 数组中的第K个最大元素
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

// @lc code=start
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
    }

    int quickSelect(vector<int>& nums, int l, int r, int index) {
        int q = partition(nums, l, r);
        if (q == index) return nums[q];
        else {
            return (q < index) ? quickSelect(nums, q + 1, r, index) : quickSelect(nums, l, q - 1, index);
        }
    }

    int partition(vector<int>& nums, int l, int r) {
        int x = nums[r];
        int i = l - 1;

        for (int j = l; j < r; j++) {
            if (nums[j] < x) {
                swap(nums[++i], nums[j]);
            }
        }
        swap(nums[i + 1], nums[r]);
        return i + 1;
    }
};
// @lc code=end

